package com.lw.leetcode.tree.b;


import com.lw.leetcode.linked.Node;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 133. 克隆图
 *
 * @Date 2021/4/29 13:42
 * @Version 1.0
 */
public class CloneGraph {


    public static void main(String[] args) {
        CloneGraph test = new CloneGraph();
        Node a = new Node();
        a.val = 1;
        Node b = new Node();
        b.val = 2;

        a.neighbors = new ArrayList<>();
        a.neighbors.add(b);
        b.neighbors = new ArrayList<>();
        b.neighbors.add(a);
        a.flag = 1;
        b.flag = 2;
//        System.out.println(a);


        Node node = test.cloneGraph(a);
        System.out.println();

//        System.out.println(node);


    }

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Node n = new Node(node.val);
        Map<Integer, Node> map = new HashMap<>(128, 1);
        map.put(node.val, n);
        find(node, n, map);
        return n;
    }

    private static void find(Node node, Node copy, Map<Integer, Node> map) {
        List<Node> neighbors = node.neighbors;
        if (neighbors != null) {
            List<Node> newList = new ArrayList<>(neighbors.size());
            for (Node neighbor : neighbors) {
                int val = neighbor.val;
                Node n = map.get(val);
                if (n == null) {
                    n = new Node(val);
                    map.put(val, n);
                    find(neighbor, n, map);
                }
                newList.add(n);
            }
            copy.neighbors = newList;
        }
    }

}
